package com.brett.frame.learn.sort.exchange;

import com.brett.frame.learn.sort.base.BaseSort;
import com.brett.frame.learn.util.DataBuilder;

/**
 * 快速排序
 * @author lenovo
 *
 */
public class QuickSort extends BaseSort {
	DataBuilder builder = new DataBuilder();

	public int[] sort(int[] arr) {
		subSort(arr, 0, arr.length - 1);
		return arr;
	}

	private void subSort(int[] arr, int left, int right) {
		int base = arr[left];
		int l=left;
		int r=right;
		if (l >= r)
			return;
		while (l != r) {
			while (arr[r] >= base && r > l) {
				r--;
			}
			while (arr[l] <= base && r > l) {
				l++;
			}
			if (l >= r)
				break;
			super.exchange(arr, l, r);

		}
		arr[left] = arr[r];
		arr[r] = base;
//		builder.printArr("i" + l, arr);
		if (l - 1 > 0) {
			this.subSort(arr, left, l - 1);
		}
		if (r + 1 < right) {
			this.subSort(arr, r + 1, right);
		}
	}
}
